# 222.完全二叉树的节点个数
# 给你一棵完全二叉树的根节点root ，求出该树的节点个数。
# 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
# 若最底层为第h层，则该层包含1~ 2h个节点。
#
# 示例1：
# 输入：root = [1, 2, 3, 4, 5, 6]
# 输出：6
#
# 示例2：
# 输入：root = []
# 输出：0
#
# 示例3：
# 输入：root = [1]
# 输出：1


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def countNodes(self, root) -> int:
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            return left + right + 1
        count = dfs(root)
        return count

    def countNodes2(self, root) -> int:
        # 这不是随便找个遍历，然后把他的值的长度求出来不就行了么，是我哪里会错意了？
        res = []
        def rev(root):
            if not root:
                return
            rev(root.left)
            rev(root.right)
            res.append(root.val)
        rev(root)
        rr = len(res)
        return rr

    def countNodes3(self, root) -> int: # 层序遍历还是简单啊
        res = 0
        if not root:
            return res
        from collections import deque
        que = deque()
        que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                res += 1
        return res

if __name__ == '__main__':
    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a21 = TreeNode(9)
    a22 = TreeNode(20,a31)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    # res = tmp.countNodes(root=a11)
    # res = tmp.countNodes2(root=a11)
    res = tmp.countNodes3(root=a11)
    print(res)